{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# 第7章 支持向量机"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 习题7.1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "&emsp;&emsp;比较感知机的对偶形式与线性可分支持向量机的对偶形式。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答：**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答思路：**\n",
    "1. 列出感知机的原始形式；\n",
    "2. 写出感知机的对偶形式；\n",
    "3. 列出线性可分支持向量机的原始形式；\n",
    "4. 写出线性可分支持向量机的对偶形式；\n",
    "5. 比较感知机和线性可分支持向量机的对偶形式。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答步骤：**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第1步：感知机的原始形式**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;根据书中第2.3.1节的感知机学习算法的原始形式：\n",
    "> 给定一个训练数据集\n",
    "> \n",
    "> $$ T=\\{(x_1,y_1),(x_2,y_2),\\cdots,(x_N,y_N)\\} $$\n",
    "> \n",
    "> 其中，$x_i \\in \\mathcal{X} = R^n, y_i \\in \\mathcal{Y}=\\{-1,1\\}, i=1,2,\\cdots,N$，求参数$w,b$，使其为以下损失函数极小化问题的解\n",
    "> \n",
    "> $$ \\min \\limits_{w,b} L(w,b)=-\\sum_{x_i \\in M} y_i(w \\cdot x_i + b) $$\n",
    "> 其中$M$为误分类点的集合。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;根据书中第2章的算法2.1：\n",
    "\n",
    "> **算法2.1（感知机学习算法的原始形式）**  \n",
    "> 输入：训练数据集$T=\\{(x_1,y_1),(x_2,y_2),\\cdots,(x_N,y_N)\\}$，其中$x_i \\in \\mathcal{X} = R^n, y_i \\in \\mathcal{Y}=\\{-1,+1\\}, i=1,2,\\cdots,N$；学习率$\\eta$（$0 < \\eta \\leqslant 1$）；  \n",
    "输出：$w,b$；感知机模型$f(x)=\\text{sign}(w \\cdot x + b)$  \n",
    "（1）选取初值$w_0,b_0$；  \n",
    "（2）在训练集中选取数据$(x_i, y_i)$；  \n",
    "（3）如果$y_i(w \\cdot x_i +b) \\leqslant 0$，\n",
    "> $$ w \\leftarrow w + \\eta y_i x_i \\\\\n",
    "b \\leftarrow b + \\eta y_i $$  \n",
    ">（4）转至步骤（2），直至训练集中没有误分类点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第2步：感知机的对偶形式**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;根据书中第2章的算法2.2：\n",
    "\n",
    "> **算法2.2（感知机学习算法的对偶形式）**  \n",
    "> 输入：线性可分的数据集$T=\\{(x_1,y_1),(x_2,y_2),\\cdots,(x_N,y_N)\\}$，其中$x_i \\in R^n, y_i \\in \\{-1, +1\\}, i=1,2,\\cdots,N$；学习率$\\eta$（$0 < \\eta \\leqslant 1$）；\n",
    "输出：$a,b$；感知机模型$\\displaystyle f(x)=\\text{sign} \\left( \\sum_{j=1}^N \\alpha_j y_j x_j \\cdot x + b \\right)$，其中$\\alpha = (\\alpha_1, \\alpha_2,\\cdots, \\alpha_N)^T$  \n",
    "（1）$\\alpha \\leftarrow 0,b \\leftarrow 0$；  \n",
    "（2）在训练集中选取数据$(x_i, y_i)$；  \n",
    "（3）如果$\\displaystyle y_i\\left( \\sum_{j=1}^N \\alpha_j y_j x_j \\cdot x + b \\right) \\leqslant 0$，\n",
    "> $$ \\alpha_i \\leftarrow \\alpha_i + \\eta \\\\\n",
    "b \\leftarrow b + \\eta y_i $$  \n",
    ">（4）转至（2），直至训练集中没有误分类数据。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;根据书中第2.3.3节对偶形式的基本思想\n",
    "\n",
    "> 从学习过程不难看出，最后学习到的$w,b$可以分别表示为\n",
    "> $$ w=\\sum_{i=1}^N \\alpha_i y_i x_i\\\\ \n",
    "b=\\sum_{i=1}^N \\alpha_i y_i $$\n",
    "> 这里，$\\alpha_i \\geqslant 0, i=1,2,\\cdots,N$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;综上所述：\n",
    "1. 感知机的原始形式中的损失函数：\n",
    "$$\n",
    "\\min_{w,b} L(w,b)=-\\sum_{x_i \\in M} y_i(w \\cdot x_i + b)\n",
    "$$\n",
    "2. 感知机的对偶形式中的损失函数：可知$w,b$表示为$\\langle x_i,y_i \\rangle$的线性组合形式，则\n",
    "$$\n",
    "\\min_{w,b} L(w,b) = \\min_{\\alpha} L(\\alpha) = - \\sum \\limits_{x_i \\in M} ( y_i ( \\sum_{j=1}^N \\alpha_j y_j x_j \\cdot x_i + \\sum_{j=1}^N \\alpha_j y_j ) )\n",
    "$$\n",
    "其中，$\\alpha = (\\alpha_1, \\alpha_2,\\cdots, \\alpha_N)^T$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第3步：线性可分支持向量机的原始形式**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;根据书中第7.1.3节的线性可分支持向量机学习的最优化问题，可作为原始最优化问题(7.13)~(7.14)：\n",
    "> $$ \\begin{align}\n",
    "\\displaystyle \\min_{w,b} \\quad & \\displaystyle \\frac{1}{2} \\|w\\|^2 \\tag{7.13} \\\\\n",
    "\\text{s.t.} \\quad & y_i(w \\cdot x_i + b) -1 \\geqslant 0, \\quad i=1, 2,\\cdots, N \\tag{7.14} \\\\\n",
    "\\end{align} $$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第4步：线性可分支持向量机的对偶形式**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;根据书中第7章的算法7.2：\n",
    "\n",
    "> **算法7.2（线性可分支持向量机学习算法）**  \n",
    "> 输入：线性可分训练集$T=\\{(x_1,y_1),(x_2,y_2), \\cdots, (x_N,y_N)\\}$，其中$x_i \\in \\mathcal{X} = R^n$，$y_i \\in \\mathcal{Y} = \\{-1, +1\\}$，$i=1,2,\\cdots, N$；  \n",
    "输出：分离超平面和分类决策函数。  \n",
    "（1）构造并求解约束最优化问题\n",
    "> $$ \\begin{array}{cl} \n",
    "\\displaystyle \\min_{\\alpha} & \\displaystyle \\frac{1}{2} \\sum_{i=1}^N \\sum_{j=1}^N \\alpha_i \\alpha_j y_i y_j (x_i \\cdot x_j) - \\sum_{i=1}^N \n",
    "\\alpha_i \\\\\n",
    "\\text{s.t.} & \\displaystyle \\sum_{i=1}^N \\alpha_i y_i = 0 \\\\\n",
    "& \\alpha_i \\geqslant 0, \\quad i=1,2,\\cdots,N\n",
    "\\end{array} $$\n",
    "> 求得最优解$\\alpha^*=(\\alpha_1^*, \\alpha_2^*, \\cdots, \\alpha_N^*)^T$。  \n",
    ">（2）计算\n",
    "> $$ w^* = \\sum_{i=1}^N \\alpha_i^* y_j x_i $$\n",
    "> 并选择$\\alpha^*$的一个正分量$\\alpha_j^* > 0$，计算\n",
    "> $$ b^*=y_i-\\sum_{i=1}^N \\alpha_i^* y_i (x_i \\cdot x_j) $$\n",
    ">（3）求得分离超平面\n",
    "> $$ w^* \\cdot x + b^* = 0 $$\n",
    "> 分类决策函数：\n",
    "> $$ f(x) = \\text{sign}(w^* \\cdot x + b^*) $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "综上所述：\n",
    "1. 线性可分支持向量机的原始形式中的损失函数：\n",
    "$$\n",
    "\\min_{w,b} L(w,b) = \\frac{1}{2} \\|w\\|^2\n",
    "$$\n",
    "\n",
    "\n",
    "2. 线性可分支持向量机的对偶形式中的损失函数：根据定理7.2，可知$w,b$表示为$\\langle x_i,y_i \\rangle$的线性组合形式，则\n",
    "\n",
    "$$\n",
    "\\min_{w,b} L(w,b) = \\min_{\\alpha} L(\\alpha) = \\frac{1}{2} \\sum_{i=1}^N \\sum_{j=1}^N \\alpha_i \\alpha_j y_i y_j (x_i \\cdot x_j) - \\sum_{i=1}^N \n",
    "\\alpha_i\n",
    "$$\n",
    "其中，$\\alpha = (\\alpha_1, \\alpha_2,\\cdots, \\alpha_N)^T$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第5步：感知机和线性可分支持向量机对偶形式的比较**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. 在两者的对偶形式中，$w,b$都可以表示为$\\langle x_i,y_i \\rangle$的线性组合形式；\n",
    "2. 在两者的对偶形式中，都可以通过求解$\\alpha=(\\alpha_1, \\alpha_2, \\cdots, \\alpha_N)^T$，最后代入由$x_i,y_i,\\alpha_i$表示的$w$和$b$公式中，从而求解最优化问题的解$w^*$和$b^*$；\n",
    "3. 感知机学习得到一个分隔超平面，而线性可分支持向量机学习得到所有分隔超平面中的间隔最大分隔超平面。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 习题7.2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;已知正例点$x_1=(1,2)^T,x_2=(2,3)^T,x_3=(3,3)^T$，负例点$x_4=(2,1)^T,x_5=(3,2)^T$，试求最大间隔分离平面和分类决策函数，并在图中画出分离超平面、间隔边界及支持向量。  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答：**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答思路：**\n",
    "1. 通过调用sklearn.svm的SVC类构建模型，根据题目中的数据训练模型，得到$w$、$b$和支持向量；\n",
    "2. 调用matplotlib库，画出分离超平面、间隔边界和支持向量。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答步骤：**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第1步：训练模型，得到$w$、$b$和支持向量**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "w = [[-1.  2.]]\n",
      "b = [-2.]\n",
      "support vectors = [[3. 2.]\n",
      " [1. 2.]\n",
      " [3. 3.]]\n"
     ]
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "from sklearn.svm import SVC\n",
    "\n",
    "# 加载数据\n",
    "X = [[1, 2], [2, 3], [3, 3], [2, 1], [3, 2]]\n",
    "y = [1, 1, 1, -1, -1]\n",
    "\n",
    "# 训练SVM模型\n",
    "clf = SVC(kernel='linear', C=10000)\n",
    "clf.fit(X, y)\n",
    "\n",
    "# 得到w、b和支持向量\n",
    "print(\"w =\", clf.coef_)\n",
    "print(\"b =\", clf.intercept_)\n",
    "print(\"support vectors =\", clf.support_vectors_)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可得：\n",
    "1. 最大间隔分离超平面：$-x^{(1)}+2x^{(2)}-2=0$  \n",
    "2. 分类决策函数：$f(x)=\\text{sign}(-x^{(1)}+2x^{(2)}-2)$  \n",
    "3. 支持向量：$x_1=(3,2)^T,x_2=(1,2)^T, x_3=(3,3)^T$  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第2步：在图中画出分离超平面、间隔边界和支持向量**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYYAAAEKCAYAAAAW8vJGAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAAA/iElEQVR4nO3dd3gU5fr/8fdDSEJCAOm9KV2adBAkiAhSFFCKFAs94Xssx3pUsB5Az08R1N0khBbqoYkgIgIRUECqREKvktBrAiEhZe/fHwk5BimBJDu7yf26rrmuzc7s5MMYc2dmnrkfIyIopZRS1+WzOoBSSinXooVBKaVUBloYlFJKZaCFQSmlVAZaGJRSSmWghUEppVQG+a0OkFUlSpSQKlWqWB1DKaXcyrZt286JSMmbrXP7wlClShW2bt1qdQyllHIrxpg/b7VOLyUppZTKQAuDUkqpDLQwKKWUykALg1JKqQy0MCillMpAC4NSSqkMtDAopZSbSUxM5MKFCzm2fy0MSinlJqKiohg1ahSVK1fmrbfeyrHv4/YPuCmlVG4mIhhjAHj77beZM2cOXbp0oXfv3jn2PfWMQSmlXNCFCxf44osvqFmzJjt37gTgo48+4vDhwyxdupQOHTrk2PfWMwallHIhW7ZswW63M2fOHBISEmjZsiVXr14F4IEHHnBKBi0MSillseuXi65cuUK7du0AeP755wkICKBBgwZOz6OFQSmlLHLgwAGCgoLYsWMHq1atws/Pj++//56HHnqIIkWKWJZL7zEopZQTJScns3jxYjp27EiNGjWYOHEiJUqUSL9c5O/vb2lRAD1jUEopp5o3bx79+/enQoUKfPzxxwwePJiyZctaHSsDLQxKKZVDRIR169Zhs9l4+OGHeemll+jRowfffvstXbt2JX9+1/wVrJeSlFIqm8XGxmKz2ahXrx7+/v6sXLmSxMREAHx8fOjevbvLFgXQMwallMp2/fr1Y9myZTRu3JgpU6bQp08ffH19rY6VaXrGoJTK865cuUJkZCQRERGcO3furj577do1Zs+ejb+/P8ePHwfg/fffZ9OmTWzdupUXX3zRrYoC6BmDUioP27VrFxMnTmTevHmUK1cODw8PoqKiaNeuHf/4xz/Snym4maNHjxISEkJoaChnz56lWrVq/Pnnn5QvX56mTZs68V+R/fSMQSmVJ82dO5d27dpRsWJF9uzZw65du/jjjz+IioqiY8eODBo0iPfeew8R+dtnL1y4QI0aNfj0009p1aoVK1asYN++fbRq1cqCf0n20zMGpdzJ1auQlAQWj3N3d+Hh4bzyyiusXr2aevXqpb6Zdmz9ihRh+PDh9OzZk8cee4zixYszcOBApk6dyv79+5k0aRLFihVj6tSptGnThkqVKln7j8kJIuKUBSgAbAYigF3AhzfZxgATgYPAH0CjO+23cePGolSud+6cyFNPiXh5iXh6itSrJ7Jli9Wp3FaLFi1k4cKFqV+cPi3SuXPqcfX0FHnoIZEdO8ThcMiCBQvEy8tLvL29BRB/f39JSEiwNnw2AbbKrX5f32pFdi9pv/T90l57ApuAFjds0xlYnrZtC2DTnfarhUHleg6HSMOGqb+04H9LoUIi0dFWp3M727Ztk0qVKklycrJISopIzZoi+fNnPLaFC8vkL78UQPLnzy/+/v4SGRlpdfRsdbvC4LR7DGlZrqR96Zm23Hjx7ikgLG3b34D7jDGu9UigUs62eTMcOJB6CemvEhMhKMiaTG5s1apV9OzZEw8PD1i7Fo4fh+Rk9gEvAwsAkpJ48vx5bDYbdrudkiVL8uCDD1ob3ImcevPZGONhjNkBnAFWisimGzYpD0T95evotPdu3M8wY8xWY8zWs2fP5lhepVzC4cOQ7yb/q167Bnv2OD+Pm7ty5Qr33XcfAEn797MwMZH2QC3ADuwBiI+nRFQUAQEBlClThri4OMvyWsGphUFEUkSkIVABaGaMqXvDJuZmH7vJfkJEpImINClZsmQOJFXKhTRsCMnJf3/fxwceftjpcdxd0aJFOXnyJABdp03jmcREDgJjSP1LdBRAwYLQsiUAJ0+epGjRohaltYYlw1VF5BKwBuh0w6pooOJfvq4AnHBOKqVcVO3a8PjjqYXguvz5U0cmDRpkXS43IyKEh4fz888/M3/+fOLj43l51CiWNmjA4QIF+BdQClKPbbFi0L8/AGFhYfTs2dPK6E7ntMJgjClpjLkv7bUP8Biw94bNlgDPmVQtgBgROemsjEq5rPnz4Z13oHx5KFoUnn0Wtm3TYauZcOnSJSZOnEjt2rVp374969evp2bNmkyePJnOnTvTddMmPN54A8qWTS0Izz0HW7ZAwYJs3LiRI0eO8OSTT1r9z3CuW92Vzu4FqA/8Tuow1EhgdNr7I4AR8r+RS98Ah4CdQJM77VdHJSmlbuX48ePi6+srgLRo0ULCwsIkPj5eIiMjpWTJkrJ06dJbfnbnzp1Srlw5WbRokRMTOw+3GZVkUte7ryZNmsjWrVutjqGUcgEJCQnMmzePqKgo3n33XQDGjh1Lp06deOihhzJsu3nzZrp3706bNm0IDAykdevWGGPYvXs3QUFBzJkzh4kTJ9I/7ZJSbmOM2SYiTW66TguDUsrdHTp0iODgYKZMmcL58+dp0KABW7duvWNr69jYWGbMmIHdbmfPnj0YYyhbtiyDBg1i6NChVKhQwUn/AufTwqCUyrUmTZrE8OHDyZcvH927dycwMJB27dphzM0GOd6aw+HA4XC49DwJ2el2hSFvHAGlVK5x5swZJk+eTOvWrWnTpg2PPvooo0ePZujQoZQv/7fHnjItX7585LvZ8yJ5kB4FpZTLExF+/fXX9LmS33nnHVauXAnAAw88wAcffJCloqAy0jMGpZTL69KlC8uXL6dIkSIEBgYyYsQIatWqZXWsXEvPGJRSLmfXrl289dZbJKX1h3rmmWcICQnh+PHjfPnll1oUcpieMSilXEJiYiKLFy/GZrOxdu1avL29eeaZZ2jatCmD9Alvp9IzBqWU5Y4cOUKlSpXo06cPx44d47PPPiM6Otrtp8h0V3rGoJRyOofDwapVqzh58iTPP/88lStX5sknn6RHjx507NhRRwdZTJ9jUEo5zYULF5g2bRp2u52DBw9Ss2bN9AfLlHPd7jkGLctKKacIDQ2lfPnyvPbaa5QuXZqZM2cSERGhRcEFaWFQSuWIq1evMnXqVHbv3g1A/fr1eeGFF4iIiEh/JsHb29vilO4pLi6OSZMmcfHixRzZvxYGpVS22r9/P//85z8pX748gwYNYs6cOQA0a9YMu91O/fr1LU7ovvbs2cNLL71EuXLlGDZsGN9++22OfB+9+ayUyjbPPPMMCxcuJH/+/Dz99NMEBATwyCOPWB3LrSUlJaUP412zZg1eXl706tWLwMBAWqbNMpfdtDAope7ZyZMnWbhwISNHjsQYQ4MGDWjYsCFDhgyhTJkyVsdza9HR0UyaNIlJkyZx8uRJKleuzLhx4xg0aBA5PaWxFgal1F0REdatW4fNZmPRokUkJyfzyCOPUL9+fUaNGmV1PLfmcDgIDw/HZrOxZMkSHA4HnTp1YtKkSXTq1AkPDw+n5NDCoJTKtP3799OjRw92795N0aJFeemllxgxYgTVq1e3Oppbu3jxItOnT8dut7N//36KFy/O66+/zvDhw6latarT82hhUErdVkREBKdOnaJjx45UqlSJChUq8MYbb9CnTx98fHysjufWtm3bhs1mY86cOcTHx9OyZUtmzJjBM888Q4ECBSzLpYVBKfU3165dY8GCBdhsNjZs2ECdOnWIjIykQIECrFixwup4bi0+Pp558+Zhs9nYvHkzvr6+DBgwgICAgL9NP2oVHa6qlMpg+vTpVKhQgQEDBnDmzBm++OILfvnlF30QLYsOHjzI66+/ToUKFXjhhReIjY1l4sSJnDhxgpCQEJcpCqBnDErleQ6HgxUrVlC/fn3Kly9P8eLFefjhhxk5ciTt27fXvkVZkJKSwrJly7DZbKxYsYL8+fPTvXt3Ro4cSdu2bV222GqvJKXyqHPnzjFlyhSCgoI4cuQIH3/8Me+9957VsXKF06dPM3nyZIKDgzl27BjlypVj+PDhDBkyhHLlylkdD9A5n5VSfyEiDB48mNmzZ3Pt2jXatm3LuHHj6N69u9XR3Nr16UdtNhsLFy4kKSmJ9u3bM378eLp164anp6fVETNNC4NSeUBcXByrV6/mySefxBhDvnz5GDJkCCNGjKBu3bpWx3NrsbGxzJw5E7vdTmRkZK6YflQLg1K52N69e7Hb7UybNo3Y2Fj2799P9erVCQ0NtTqa29u5cyd2u50ZM2Zw5coVHnroIUJDQ+nbty8FCxa0Ol6WaGFQKhfav38/AQEBhIeH4+npmd5bp1q1alZHc2uJiYksWrQIm83GL7/8gre3N3379iUgIIBmzZq57M3ku6WFQalcIjo6mjNnztCoUSNKlCjByZMnGTt2LIMGDaJUqVJWx3Nrx44dIyQkhEmTJnHmzBnuv/9+/vOf//Diiy9SvHhxq+NlO6cVBmNMRSAMKAM4gBARmXDDNv7Ad8CRtLcWichHzsqolLsRkfTeOt999x2NGzdm06ZNFCtWjF27duWav2Ct4HA4WLlyJTabje+//x6ALl26EBgYyOOPP56rh/E684whGXhNRLYbYwoB24wxK0Vk9w3b/SIiXZ2YSym3NG/ePEaPHs2+ffsoXrw4//znPxkxYkT6ei0K9+b8+fNMnTqVoKAgDh06RKlSpXjrrbcYPnw4lStXtjqeUzitMIjISeBk2uvLxpg9QHngxsKglLqF7du388ADD1CkSBFiY2MpVqwYYWFh9OrVy9LeOu5ORNiyZQs2m425c+dy7do12rRpwyeffELPnj3x8vKyOqJziYjTF6AKcAwofMP7/sB5IAJYDjx4i88PA7YCWytVqiRK5Wbx8fEyffp0ad68uQAyceJEERFxOBwWJ3N/cXFxEhoaKo0aNRJA/Pz8JCAgQP744w+ro+U4YKvc6nf0rVbk1AL4AduAnjdZVxjwS3vdGThwp/01btw4Bw6ZUtZLTk6WN954Q4oXLy6A1KpVSyZMmCAXL160Oprb27t3r7z88sty3333CSB169YVm80mMTExVkdzmtsVBqeOSjLGeAILgVkisujG9SIS+5fXPxhjbMaYEiJyzpk5lbJKSkoKO3bsoHHjxnh4eLBt2zbatWtHYGAg/v7+et8gC5KTk1myZAk2m43Vq1fj6enJM888Q0BAAK1bt9Zj+xfOHJVkgMnAHhH54hbblAFOi4gYY5qR2v31vLMyKmWVv/bWOXnyJFFRUZQuXZqffvrJabN25VYnTpwgNDSUkJAQjh8/TsWKFfnkk08YMmQIpUuXtjqeS3LmGcPDwEBgpzFmR9p77wCVAEQkCHgGCDDGJAPxQN+0Ux6lcqWDBw8yevRoFixYkKG3TrFixQC0KNwjEWHNmjXYbDYWL15McnIyHTt2xGaz0aVLFz2ud+DMUUm/Arc9VxORr4GvnZNIKWtcvnyZCxcuULlyZTw8PPjxxx/dvreOq4iJiSEsLAy73c6ePXsoVqwYr7zyCsOHD9envu+CPvmslJNERkZit9sJCwvD39+fpUuXUrVqVU6dOpX3hkNmsx07dmC325k5cyZXr16lWbNmTJs2jd69e+v0o/dAC4NSOWzZsmV89tlnrFu3LkNvneu0KNyba9euMX/+fGw2Gxs3bqRAgQL069ePgIAAmjS56TQDKpO0MCiVA44dO0aZMmXw8vIiIiKC6OhoPvvsMwYNGpQre+s405EjRwgODmby5MmcO3eO6tWr88UXX/DCCy9QtGhRq+PlCjqDm1LZ5MbeOnPmzKF3794kJCTg5eWVq3vr5LSUlBR+/PFHbDYby5cvxxjDU089RWBgII8++qge23ugM7gplYMSExP56quvsNvtHDp0iJIlS/LWW2/RsmVLAG1VkQVnz55NH8Z79OhRypQpw6hRoxg6dCgVKlSwOl6upYVBqXsgIhw/fpwKFSrg6elJaGgoZcuW5aOPPuLpp5/G29vb6ohuS0TYuHEjNpuN+fPnk5iYiL+/P59++ik9evRwqyky3ZUWBqXuwtWrV5k7dy42m42DBw9y/PhxChYsyKZNmyhcuLDV8dzalStXmDVrFna7nYiICAoXLszw4cMZMWIEderUsTpenqKFQalMOHbsGOPHj2fatGlcunSJBx98kDFjxqRf29aicO92796N3W5n+vTpXL58mQYNGhAcHEy/fv3w8/OzOl6epIVBqVtITk7m8uXLFC1alDNnzvD111+n99Zp06aN9tbJgqSkJBYvXozNZmPNmjV4eXnRu3dvAgMDadGihR5bi2lhUOoGJ0+eZNKkSYSEhNCxY0cmT55MkyZNOHnyJCVKlLA6nluLjo5OnyLz1KlTVKlShXHjxjFo0CBKlixpdTyVRguDUml+/fVXJk6cyLfffpveW+fpp59OX69F4d44HI706UeXLFmCw+Ggc+fOBAYG0rFjR+1b5IK0MKg8LTY2lkKFCmGMYf78+axevVp762STixcvMn36dOx2O/v376dEiRK8/vrrDB8+nKpVq1odz62dP3+eK1eu5NxUo7eaqMFdFp2oR92LHTt2yLBhw6RgwYLy888/i4jI+fPn5erVq9YGywW2bt0qgwYNEh8fHwGkZcuWMnPmTElISLA6mtvbvHmzPPfcc+Lt7S19+/bN0r5wlYl6lLJSUlIS8+bNw2azsWHDhvTeOmXLlgVIb3Wt7l58fDz//e9/sdvtbN68GV9fXwYOHEhAQAANGza0Op5bu3r1Kj4+PhhjCA0NZdGiRQwePDhDv63spi0xVK539epVfH19SUxMpFKlShQuXJiAgACef/55LQZZdPDgQYKCgpg6dSoXLlygVq1aBAYG8txzz1GkSBGr47m1ffv2YbfbmTZtGj/++CMtWrTgzJkz+Pj4UKhQoSzvX1tiqDznem8du93Orl27OHjwIF5eXmzYsIEqVapob50sSE5OZtmyZdjtdlasWEH+/Pnp3r07I0eOpG3btjrUNAuSk5P57rvvsNvt6dOPPv300+nPyZQqVcopObQwqFzl3LlzTJ48maCgoPTeOkOHDiUhIYGCBQty//33Wx3RbZ06dSq9b1FUVBTlypXjww8/ZMiQIZQrV87qeG4tMTERLy8vkpKSGDZsGH5+fvz73/9m8ODBlkw/qoVBuT0RISkpCS8vLzZt2sTbb7+Nv78/n332Gd27d9feOlkgIvzyyy/YbDYWLlxIcnIyjz32GBMmTKBbt27kz6+/Qu6ViPDzzz9js9nYvXs3kZGR+Pj48Ouvv1KjRg1Lh/Hqf1Xltq5cucLs2bOx2Ww88cQTjB07lk6dOrF7925q165tdTy3Fhsby8yZM7HZbOzatYsiRYrwf//3f4wYMYKaNWtaHc+tXbp0KX360b1791KsWDEGDx5MQkICvr6+LvGzq4VBuZ09e/ak99aJjY2lfv361KtXDwAPDw+X+B/LXe3cuRObzcbMmTO5cuUKjRo1IjQ0lGeffRZfX1+r47m1lJQUPDw8CA8P5+WXX6ZFixaEhYXRq1cv12vNfqtxrO6y6HMMeUNycnL66759+4qXl5f0799f1q9fLw6Hw8Jk7i8hIUFmz54trVu3FkC8vb3l+eefl02bNumxzaL4+HiZPn26tGjRQj744AMREUlKSpJt27ZZnOz2zzFY/os9q4sWhtwtKipKRo8eLWXLlpXIyEgRETly5IicOXPG4mTu7+jRo/Kvf/1LSpYsKYA88MAD8p///EfOnTtndTS3d+jQIXnjjTekePHiAkiNGjVk2rRpVsfK4HaFQS8lKZcjIqxevTpDb50nnniClJQUAKpUqWJtQDfmcDj46aefsNlsLFu2DIBu3boREBBAhw4ddBhvFohI+lDd1157jaVLl9K9e3cCAgJ49NFH3WoYrz7gprJVdHQ0f/zxB0lJSZQvX57GjRtn+n8Ih8NBvnz5iImJoVy5cvj4+DBkyBCGDRumw0yz6Pz580ydOpWgoCAOHTpEqVKlGDp0KMOGDaNSpUpWx7PckSNH2L17NykpKVSpUoV69epl+uf2zJkzTJkyhZCQEFasWEH16tXZv38/BQsWpHz58jmc/N7d7gE3yy8FZXXRS0muYf369dK9e3cpWrSoPP7449K1a1epXr261KlTR7755htJSkq65We3bt0qgwcPltatW6df0964caPEx8c7K36u5HA45LfffpPnn39evL29BZA2bdrInDlz5Nq1a1bHcwkrV66Ujh07SokSJaRTp07StWtXqVy5sjRq1EimTp16y3ssDodDfv31V+nfv794eXkJII8++qj8/vvvzv0HZAF6j0HlpKlTp0qZMmUkKChILl++nP6+w+GQ8PBweeSRR6Rbt24ZmqhdvXpVpk2bJs2aNRNAfH19ZejQoVoMskFcXJyEhoZKo0aNBBA/Pz8JDAyUnTt3Wh3NpXz++edSsWJFmT59eobmiSkpKfLDDz9I48aNZeDAgRkGPlwvFOfPnxdvb28pXLiw/OMf/5Ddu3c7PX9WaWFQOWbVqlVStmxZ2bdv3//ePHJEJCJCJDFRREQSExOle/fuMmTIkPT/saZNmyaA1KpVSyZOnCgXL150fvhcZu/evfLyyy9LkSJFBJC6deuKzWaT2NhYq6O5nHnz5kmVKlUkKioq/b0DB0R27hS5Xgfi4uLE399f3n77bYmMjJSRI0dKp06d0rcPDw/P8IeQu3GJwgBUBH4G9gC7gJdvso0BJgIHgT+ARnfarxYGa7Vt21bmzp2b+kVUlEiTJiI+PiJ+fiJFi4osXChJSUkyZ84c8fT0lNGjR4tI6hlDeHi4DofMosTERFmwYIG0b99eAPH09JS+ffvK2rVr9djegsPhkAcffFBWrVolIiL794vUqSPi65v6Y1uqlMjKlSLXrl2T4OBg8fDwSB/GO3DgwFxzGc5VCkPZ67/ogULAfqDODdt0BpanFYgWwKY77VcLg3UiIyOlbNmykpiYKOJwiNSqJeLhkfpjBXIS5BNPT6lYpowAUrBgwQx/cal7d/z4cfnggw+kXLlyAkjFihXl3//+t5w6dcrqaC5v7dq1UqtWLXE4HJKUJFK2rIgx6T+2AiIFC4qMGzcp/VJc165d5ezZs1ZHz1a3KwxOG64qIieBk2mvLxtj9gDlgd1/2ewpICwt9G/GmPuMMWXTPqtczIYNG+jUqVNqL6LNmyE6GtKGlAI8B6xMSuIxDw8mLFqEn58fn3zyiXWB3ZzI/3rrLF68mJSUFDp27IjdbqdLly46RWYmrV+/nm7dumGM4aefIC4ORBzAasAGPEFS0jAuXerDsmXliI2NZf78+XlqaldLBi0bY6oADwGbblhVHoj6y9fRae/d+PlhxpitxpitZ8+ezbGc6vbi4+MpWLAgALGHD2NLTqYRadUf+AzYC6ysV48ePXpQqFAhEhISLErrvi5dusTEiROpU6cO7du35+eff+bVV1/lwIED/Pjjjzz55JNaFO7C9Z5EAIcOXSQhYTxQC3gc+BVIIjERTp8uROfOnfHz88tzP7dOf8DNGOMHLAReEZHYG1ff5CN/e9BCREKAEEh9jiHbQ6pMKV26NAsWLCAwMJAZYWFcSUigEXCK1OuGDQF8feGJJwA4evSo0/rJ5wa///47NpuN2bNnc/XqVZo1a8a0adPo3bs3Pj4+VsdzW6VKlWLLli0AzJr1NImJPwMPAx8ATwPe+PnBY4+lbp8nf25vdY0pJxbAE1gB/PMW64OBZ//y9T6g7O32qfcYrHPw4MGMvXX69xeHr+//LtR6e4tUrSqSNirmsccek9mzZ1uc2rXFx8dLWFiYtGjRQgDx8fGRwYMHy9atW62O5vbi4uJkypQp0rRpUylSpIhcunRJNm7cKF277pC//tgWKCDSoIHItWupN6obNmwoP/30k9Xxsx3ZcfMZKAk8AHhm9jM3fN4AYcCXt9mmCxlvPm++0361MDjP0aNH5Z133pHnnnsu/b1OnTrJ4MGDU79wOET++1+RVq1EHnxQ5L33RC5cEBGRDRs2SOnSpXVC+Fu4WW+d8ePHy4W046fu3f79++Wf//ynFC1aVACpU6eOdOjQIb2pXUqKyNSpIs2aidSrJzJmjMiVK6mfXbp0qVSvXl1SUlKs+wfkkCwVBmAYMIPUSzefAbNIvUNT9U6fvWE/rUm9LPQHsCNt6QyMAEbI/4rHN8AhYCfQ5E771cKQs1JSUmT58uXSrVs3yZcvn+TLl0+6d++eOhJJRM6dOyfVq1eXTz755JbDIzdv3ixlypSRpUuXOjO6y0tOTpalS5fKE088IcYY8fDwkJ49e8qqVat0qGk2OXHihOTLl0/y588vvXv3ljVr1ojD4ZBjx45JhQoVxG633/Kz4eHhUrJkSVm3bp0TEztPVgvD354lAAoC1e/0WWcsWhhy1ldffSWAlCpVSt599135888//7bN8ePHpXHjxtKgQQMJCgqSQ4cOSVRUlKxcuVKeeeYZKVq0qCxevNiC9K7p9OnTMnbsWKlcubIAUrZsWRk9enSGh63UvTl58qR8/PHHEhgYmP7ejBkz5OTJk3/b9uDBg1KrVi1p3ry5TJ8+XY4cOSLHjh2T77//Xrp27SolS5aU8PBwZ8Z3qqwWhg7AJKBB2tfD7vQZZy5aGLKPw+GQTZs2yfPPPy/z5s0TEZGzZ89mqrdOSkqK/PTTT9K9e3epXLmylC1bVpo2bSpff/21xMTEOCO+S3M4HLJ+/foMvXXatWsn8+fPTz/7UvfG4XDImjVrpHfv3pI/f34BpFOnTrftz3VdcnKyLFmyRDp37iyVKlWS8uXLS6tWrSQ0NFTi4uKckN46WS0M3wL3Af8PeBSw3ekzzly0MGTd9d46jRs3Tn+gZ/z48VbHyhUuX74sQUFB0qBBAwHcureOq5owYYIAct9998mrr76asT2LuqXbFYbMDFc9KyKXgNeNMeOAppn4jHIjHTt25Ndff6Vu3brYbDYGDBhAoUKFrI7l1nbt2oXdbicsLIzLly/ToEEDgoOD6devH35+flbHc2sRERHpD/V169aNXr16UahQIfr06aPTj2aTzBSGZddfiMjbxph/5GAelcOSk5NZsmQJU6dOZfbs2RQqVIjRo0dToEABWrdu7VaTibiaxMREvv32W+x2O2vXrsXLy4vevXsTGBhIixYt9NhmwbVr11iwYAF2u53169dToEABatSoAUDZsmV58cUXLU6Yy9zqVOL6AhS4m/edveilpMw5fvy4fPjhh1K+fPn03jrbt2+3OlaucOzYMXnvvfekTFpPqCpVqsi4ceN0+tFs4nA4pFWrVgJItWrV5PPPP5fz589bHcvtkcVLSeOMMQ5SexpdAqqmLbOA9dlfqlR2+/PPP6lWrRrJycl07NiRb775hi5dupA/v87seq8cDkeG6UdFhM6dOxMYGEjHjh21RUUWOBwOVqxYwfTp05k6dSo+Pj68/fbbeHl56fSjTpKpqT2NMUVJ7XBQFDggIjtzOFem6dSefxcTE0NYWBjnzp3jww8/BODLL7+ka9euVKtWzeJ07u3ChQtMmzaNoKAgDhw4QIkSJdKnH61atarV8dzauXPnmDp1Kna7nSNHjlC6dGmWL1/OQw89ZHW0XCnbpvYEviStmLjKopeS/uf333+XoUOHiq+vrwDStm3bXPnEphW2bNkiL774ohQoUEAAadWqlcyYMUOf5M4mhw4dyjD96Ny5c3PNvAeuiuyajwH4GFgKFEz7+nFg/d3sI7sXLQypxo8fr711stnVq1fTe+uQNp/E8OHDZceOHVZHc3tXrlyRkJAQGTdunIik3kf45JNPdPpRJ8q2wpC6L/oBW0jtT7sCaHO3+8jOJa8WhsOHD8ubb74pa9euFRGRAwcOaG+dbHLgwAF57bXX0nvr1K5dW7766iu5dOmS1dHc3p49e+Sll15Kn360ZcuW2v7DItl5xtCe1Ok515Da+bTm3Xw+J5a8VBiSk5Pl+++/l86dO4sxRvLlyyeffvqp1bFyhaSkJFm8eLE8/vjjAqT31vn555/1F1c2uX5W6+npKf369ZNffvlFj62FsrMwhAOt017XI7UR3qN3s4/sXvJSYXj44YcFkDJlymhvnWxyvbdOxYoVBZAKFSrIxx9/LCdOnLA6mtuLjo6W999/X3777TcREdm9e7eMHTtWTp8+bXEyJZKNheFvH06dj2VDVvaR1SW3FobrvXUCAwPTe76EhYXJvHnztLdOFjkcDlm7dq306dMnvbdOhw4d5Ntvv81Ufx11aw6HQ1atWiU9e/YUDw8PMcak30dQriXHCkPqvvHJ6j6ysuS2wnD58mUJDg7O0FsnIiLC6li5QkxMjHz99dfy4IMPam+dHNKmTRsBpHjx4vLmm2/KoUOHrI6kbuF2hSHLTziJSHxW96FS7du3j2bNmhEbG0uDBg0ICQnh2Wef1d46WfTHH39gt9uZMWMGcXFxNG7cmClTpmhvnWywfft25s6dy7hx48iXLx8DBgxg6NCh9OrViwIFClgdT92rW1UMd1nc+YwhMTFR5s2bJyEhISKS2rr6lVdekQ0bNuhNuSxKSEiQWbNmpd+XKVCggLzwwguyadMmq6O5vfj4eJk+fbo0b95cAPH19dVhpm6InLyUZPXijoUhKipKRo0ald5bp3HjxloIssnRo0flX//6l5QsWVJ76+SAXbt2pU8/WrNmTZkwYYJcvHjR6ljqHtyuMGizHCebMGECr732Gg6HI0NvHe28ee+u99ax2WwsW7YMYwzdunVj5MiRtG/fXnvrZEFKSgo//PADsbGx9O/fnxo1atCzZ0/69u1Lu3bt9Oc2l8pUryRX5uq9ki5evMi0adN4/PHHefDBB9myZQsLFy5k+PDh2lsni6731gkKCuLw4cOULl06vW9RpUqVrI7n1s6cOcPkyZMJDg7mzz//pHHjxmzZskULQS6Sbb2SXHFx1UtJW7dulUGDBomPj48AOmQvmzgcDtm4caMMHDgwvbfOI488or11stHEiRPF09NTAHn00UdlwYIFOkQ6F0IvJTmPiNChQwdWr16Nr68vAwYMIDAwkIYNG1odza3FxcUxZ84cbDYbv//+O4UKFWLw4MEEBARQt25dq+O5tcuXLzNr1izat29P9erVadiwIQEBAQQEBFCrVi2r4ykr3KpiuMviCmcMBw4ckHHjxqXfQB47dqz21skmN/bWqVevntjtdomNjbU6mtuLjIyUwMBAKVSokAAyduxYqyMpJ0JHJWW/m/XW2bt3ryVZcpvExERZsGCBPProo9pbJwc4HA7p2LGjAOLt7S3PPfec/Pbbb3ps85jbFQa9lHQPIiMj6dy5M1FRUZQvX56PPvqIIUOGULZsWaujubXjx48zadIkQkJCOHnyJJUqVWLMmDEMGjSI0qVLWx3PrUVFRbFkyRJGjhyJMYamTZvSvn17XnzxRUqUKGF1POVqblUx3GVxxhnD9d46S5cuFZHUB3x69uwpixYt0t46WeRwOGT16tXy9NNPp/fWeeKJJ2Tp0qWSnJxsdTy3lpKSIitWrJCnnnpK8uXLJ8YY2b9/v9WxlItALyXdmxt767jC/Yzc4uLFizJhwgSpWbOmAFKsWDF544035ODBg1ZHyxX++OMPqVatmgBSsmRJ+de//iVHjhyxOpZyIbcrDHop6Ra++eYb3nrrrfTeOpMnT6Zv375Wx3J7v//+O3a7nVmzZnH16lVatGhBWFiY9tbJBlu2bCEmJobHHnuM+++/nwceeICPPvqInj174u3tbXU85U5uVTGyewGmAGeAyFus9wdiSJ3jYQcwOjP7za6/4hMSEmT27NkSHR0tIiLff/+9vPDCC7J58+Zs2X9eFh8fL2FhYdKiRYv06UeHDBki27Ztszqa24uLi5MpU6ZIkyZNBJCmTZtaHUm5CVzhUhLwCNDoDoXh+7vdb1YLw9GjR+Wdd96RUqVKCSD/+c9/srQ/9T+HDh2SN998M723To0aNWT8+PHaWyebBAUFpU8/WqdOHfnqq68kJibG6ljKTdyuMDjtUpKIrDPGVHHW97sTh8NBr169WLx4MQDdunUjMDCQxx57zNpgbi4lJYXly5djs9n48ccfyZcvH927dycgIIBHH31UWypkQXJyMt9//z2tWrWiVKlSFC9enA4dOjBy5EjatGmjx1Zln1tVjJxYgCrc/ozhPBABLAcevM1+hgFbga2VKlW654o5YsQIeffdd+XPP/+8532oVKdPn5YxY8ZI5cqVBZCyZcvK+++/n35pTt27EydOyEcffSQVKlQQQD7//HOrI6lcAFe4lCR3LgyFAb+0152BA5nZp44Uso7D4ZBffvlF+vXrp711ckBycrL07ds3ffrRxx9/XBYvXqxDpFW2uF1hcJlRSSIS+5fXPxhjbMaYEiJyzspc6u+u99ax2Wzs3LmTwoULExAQwIgRI6hdu7bV8dxaTEwMa9eu5cknn8TDw4P8+fPz0ksvMWLECKpXr251PJVHuExhMMaUAU6LiBhjmgH5SL20pFzErl27sNvthIWFcfnyZRo2bEhISAj9+vWjYMGCVsdzaxEREdhstvRhvMeOHaNChQrMmDHD6mgqD3JaYTDGzCH1PkIJY0w08D7gCSAiQcAzQIAxJhmIB/qmne4oCyUmJvLtt99is9lYt24dXl5e9OnTh8DAQJo3b643PLNo586djBgxgg0bNlCgQAGeffZZAgICqFChgtXRVB7mzFFJz95h/dfA106Ko+7g2LFjhISEEBoayunTp6latSqfffaZ9tbJBkePHiUmJoYGDRpQsmRJYmJi+OKLL3j++ecpVqyY1fGUcp1LScp6DoeDVatWYbPZWLp0KSJCly5d0qcf1Sky711KSkr69KM//PAD/v7+hIeHU6ZMGXbu3KlnXsqlaGFQXLhwgWnTpmG32zl48CAlS5bkrbfeYtiwYVSpUsXqeG5v+vTpfPjhhxw5coQyZcrw3nvvMXTo0PT1WhSUq9HCkIdt2bIFm83G3LlzSUhI4OGHH+bDDz/k6aef1t46WSAi/Pbbb9SvX5+CBQsSExNDxYoVGTduHN27d8fLy8vqiErdlnH3+7tNmjSRrVu3Wh3DbVy9epX//ve/2Gw2tm7dSsGCBRk4cCABAQHUr1/f6nhuLS4ujtmzZ2Oz2dixYwehoaEMHjwYEdGzAuVyjDHbRKTJzdbpGUMeceDAAYKCgpg6dSoXL16kTp06fP311wwcOJDChQtbHc+tJSYm8vrrrzN9+nRiY2OpX78+wcHB9OnTB9BLRcr9aGHIxa731rHZbKxcuZL8+fPz9NNPExAQwCOPPKK/sLIgKSmJiIgImjRpgpeXF9u3b6dbt24EBATQqlUrPbbKrWlhyIVOnTpFaGgowcHBREdHU6FCBT7++GOGDBlCmTJlrI7n1v46/ejFixc5ceIERYsWZe3atXh4eFgdT6lsoYUhlxAR1q1bh81mY9GiRSQnJ9OhQwe++uorunbtSv78+p86K3bv3s2oUaP47rvvcDgcdOzYkZEjR6ZfhtOioHIT/W3h5mJjY5kxYwY2m43du3dTtGhR7a2TTS5dukRsbCyVKlXCGMO6det47bXXGD58OPfff7/V8ZTKMVoY3FRERAR2u52ZM2cSFxdH06ZNmTJlCn369MHX19fqeG5t+/bt2Gw2Zs+eTdeuXZk3bx61a9fmxIkTeHp6Wh1PqRynhcGNXLt2jYULF2Kz2Vi/fn2G3jpNmza1Op7bW7RoEZ999hmbNm3C19eXAQMGEBAQkL5ei4LKK7QwuIGjR48SHBzM5MmTOXv2LNWqVePzzz/nhRde0N46WXT48GEqV66Mh4cH27ZtIyYmhgkTJvDcc89x3333WR1PKUvoA24u6npvHbvdzrJlyzDG8OSTTxIYGEj79u21b1EWpKSk8MMPP6RPP7pkyRK6detGQkIC3t7eOtRU5Qn6gJsbOXfuHFOmTCEoKIgjR45QunRp3n33XYYNG0bFihWtjufWEhIS+OKLLwgODubYsWOUK1eODz/8MP0yXIECBSxOqJRr0MLgAq731rHZbMybN4/ExETatm2rvXWygYgQHR1NxYoV8fT0JDQ0lOrVqzN+/Hi6deum9w2UugktDBa6sbdOoUKFGDp0KAEBATz44INWx3Nrly9fZubMmdhsNk6fPk1UVBTe3t5ERERQqFAhq+Mp5dK0MFhg79692O12pk+fTkxMDPXr1ycoKIj+/fvj5+dndTy3dvjwYT7//HPCwsK4cuUKDz30EGPGjElfr0VBqTvTwuAkSUlJfPfdd9jtdsLDw/Hy8qJXr14EBgbSsmVLveGZBYmJicTFxVG0aFGio6OZPHkyffv2JSAggGbNmumxVeouaWHIYX/trXPy5EkqV67M2LFjGTRoEKVKlbI6nlu7Pv3opEmT6NWrF19//TVt2rThxIkTOoxXqSzQwpADRITw8HDsdjuLFy/G4XDQqVMnQkJCeOKJJ7SvThaFh4czceLE9OlHu3btSo8ePYDUFtdaFJTKGi0M2ejSpUtMnz4du93Ovn37KFasGK+++iojRozggQcesDqeW7t06RJFihTBGMPcuXPZsGEDb775JsOHD9fpR5XKZvqAWzbYvn07drudWbNmER8fT4sWLQgMDKRXr146Nj4LRIQtW7Zgt9uZO3cua9asoXnz5pw/fx4/Pz+dflSpLNAH3HJAQkIC8+bNw2azsWnTJnx8fOjfvz8BAQE0atTI6nhu7dq1a8yaNQubzca2bdvw8/PjxRdfpGTJkgAUL17c4oRK5W5aGO7SoUOHCAoKYsqUKVy4cIGaNWtqb51sEhcXR8GCBUlJSeH111+nXLlyfPPNNwwYMECnH1XKibQwZMKNvXU8PDzo0aMHAQEBtGvXTodDZkFycjJLly7FZrMRFRXF7t278fX1Zfv27VSuXFmPrVIW0MJwG6dPn2by5MkZeut88MEHDBkyhPLly1sdz62dOnWKSZMmERwczPHjx6lYsSLDhw8nKSkJb29vvaGslIW0MNxARFi/fj02m40FCxaQlJRE+/bttbdONhAREhMT8fb25tdff2X06NF07NiRb775hi5duuj0o3eQnAy//AJxcdCmDRQpYnUilWuJiFMWYApwBoi8xXoDTAQOAn8AjTKz38aNG0t2iI2NFZvNJnXr1hVAihQpIq+88ors3bs3W/afl126dEm++uorqV27tnz00UciIpKYmCj79++3OJn72L5dpFQpkUKFRAoXFvHxEQkOtjqVcmfAVrnF71VnNvWfBnS6zfongOppyzDA7oRMREZGMnLkSMqVK0dgYCCenp5MmjSJ48ePM378eGrWrOmMGLlSREQEw4cPp3z58vzjH//Az8+POnXqAKmzoemc1JmTlASPPw5nzsDlyxAbC/Hx8OqrsGOH1elUbuS0c3cRWWeMqXKbTZ4CwtIq2W/GmPuMMWVF5GRO5Pnhhx/49NNPWbduHd7e3vTp04fAwEDtrZNFycnJ6ZeERo8ezU8//US/fv0ICAigSZObDplWd7B6NSQm/v39a9cgJARsNudnUrmbK13ULQ9E/eXr6LT3/lYYjDHDSD2roFKlSvf0zSIjI4mOjuazzz7jxRdfpESJEve0H5XqyJEjBAcHM3XqVDZs2MADDzzAl19+yX333UfRokWtjufWYmPhZs+hpqTAhQvOz6NyP1cqDDf7M/2mj2WLSAgQAqlPPt/LN3v55Zd5/fXXdYrMLEhJSeHHH3/EZrOxfPlyjDE89dRTJCUlAVC1alWLE+YO/v43P2MoWBB69nR6HJUHuNJvxWjgr3NXVgBO5NQ38/b21qJwjxwOBwAXLlygZ8+ebN++nffee4+jR4+yaNEiatWqZXHC3KVUKfjgA/D1hetXOQsWhMaNtTConOFKZwxLgP8zxswFmgMxOXV/Qd09EWHjxo3YbDZOnTrFqlWrKFmyJOvWraNRo0Y6jDeHvf02PPxw6j2FmBjo3Rv69AEd4atygtN+rIwxcwB/oIQxJhp4H/AEEJEg4AegM6nDVa8CLzorm7q1K1eupE8/GhERQeHChXnuuedISkrC09OT5s2bWx0xz2jTJnVRKqc5c1TSs3dYL8BIJ8VRdyAiGGMICwtj5MiR1K9fn+DgYPr166fTjyqVy+lFdpUuKSmJ+fPn065dO0JCQgAYMGAA69evZ8eOHQwbNkyLglJ5gF6hVERHR6dPP3rq1CmqVKmCj48PAIULF6ZVq1YWJ1RKOZMWBkXfvn3ZsGEDTzzxBIGBgXTq1EmnH1UqD9PCkMdcvHiRadOmMW3aNMLDwylevDgTJkygWLFi+tyBUgrQwpBnbNu2DZvNxpw5c4iPj6dly5acOnWK4sWL07hxY6vjKaVciBaGPODPP/+kSZMm+Pr6MnDgQAICAmjYsKHVsZRSLkoLQy508OBBgoKCuHTpEqGhoVSuXJmFCxfSvn17imgTf6XUHehw1VwiJSWFJUuW0KlTJ6pXr86ECRO4evVqevuKnj17alFQSmWKFoZc4v/9v//HU089RWRkJB999BHHjh1j9uzZ2g9KKXXX9FKSGxIRfvnlF+x2O88++yxPPvkkAwcOpEaNGnTr1k2nyFRKZYn+OelGYmNjsdls1KtXj7Zt27J8+XJOnToFQLly5ejRo4cWBaVUlulvETfi7+/P77//TqNGjZg8eTJ9+/bF19fX6lhKqVxGC4OLSkxMZOHChcyePZt58+bh4+PDmDFjKFasGE2bNtXpR5VSOUYLg4v5888/CQkJITQ0lDNnznD//fdz5MgR6tSpQ6dOnayOp5TKA7QwuJA9e/ZQt25dALp27UpgYCAdOnTQkUVKKafSwmCh8+fPM3XqVOLj4xk1ahS1atXi888/p2fPnlSqVMnqeEqpPEoLg5OJCJs3b8Zms/Hf//6Xa9eu0blz5/SJcV555RWrIyql8ji9RuFkY8aMoUWLFixatIjBgwezc+dOli1bpjeTlVIuQ88Ycti+ffsICgqib9++NG/enJ49e1KsWDEGDBhAoUKFrI6nlFJ/o4UhByQnJ7NkyRLsdjurVq3C09OTatWq0bx5c2rXrk3t2rWtjqiUUrekhSGbiQhNmjQhIiKCSpUq8cknnzBkyBBKly5tdTSllMoULQxZJCKsWbOGBQsW8NVXX5EvXz5efvllSpQoQefOnXWKTKWU2zEiYnWGLGnSpIls3brV6d83JiaGsLAw7HY7e/bsoVixYmzcuJEaNWo4PYtSSt0tY8w2EWlys3U6Kuke7Nixg3LlyvHSSy9RqFAhpk2bRnR0tBYFpVSuoJeSMiEhIYEFCxaQnJzMCy+8QN26dRk2bBj9+/enSZObFlyllHJbeinpNg4fPkxwcDCTJ0/m/Pnz+Pv78/PPP+fI91JKKWfSS0n3YMyYMVSrVo3PP/+ctm3bsmrVKsLDw62OpZRSOc6phcEY08kYs88Yc9AY8/ZN1vsbY2KMMTvSltHOynb27Fk+/fRTDhw4AMAjjzzCqFGjOHr0KAsXLqR9+/b6dLJSKk9w2j0GY4wH8A3QAYgGthhjlojI7hs2/UVEujojk4iwceNGbDYb8+fPJzExkYIFC1K9enVat25N69atnRFDKaVcijNvPjcDDorIYQBjzFzgKeDGwuAUDoeDVq1asWnTJgoXLszw4cMZMWIEderUsSKOUkq5DGcWhvJA1F++jgaa32S7lsaYCOAE8LqI7LpxA2PMMGAYcM/tqfPly0eXLl0YPHgwzz77LH5+fve0H6WUym2cWRhudoH+xiFR24HKInLFGNMZWAxU/9uHREKAEEgdlXSvgUaNGnWvH1VKqVzLmTefo4GKf/m6AqlnBelEJFZErqS9/gHwNMaUcF5EpZRSziwMW4DqxpiqxhgvoC+w5K8bGGPKmLShP8aYZmn5zjsxo1JK5XlOu5QkIsnGmP8DVgAewBQR2WWMGZG2Pgh4BggwxiQD8UBfcfcn8JRSys3ok89KKZUH6ZPPSimlMk0Lg1JKqQy0MCillMpAC4NSSqkM3P7mszHmLPDnPX68BHAuG+PkNHfK605Zwb3yulNWcK+87pQVspa3soiUvNkKty8MWWGM2Xqru/KuyJ3yulNWcK+87pQV3CuvO2WFnMurl5KUUkploIVBKaVUBnm9MIRYHeAuuVNed8oK7pXXnbKCe+V1p6yQQ3nz9D0GpZRSf5fXzxiUUkrdQAuDUkqpDPJEYTDGdDLG7DPGHDTGvH2T9cYYMzFt/R/GmEZW5EzLcqes/saYGGPMjrRltBU507JMMcacMcZE3mK9yxzXtDx3yutKx7aiMeZnY8weY8wuY8zLN9nGJY5vJrO60rEtYIzZbIyJSMv74U22cZVjm5ms2X9sRSRXL6S2+D4E3A94ARFAnRu26QwsJ3WWuRbAJhfO6g98b/VxTcvyCNAIiLzFepc4rneR15WObVmgUdrrQsB+F/65zUxWVzq2BvBLe+0JbAJauOixzUzWbD+2eeGMoRlwUEQOi0giMBd46oZtngLCJNVvwH3GmLLODkrmsroMEVkHXLjNJq5yXIFM5XUZInJSRLanvb4M7CF13vS/conjm8msLiPteF1J+9IzbblxFI6rHNvMZM12eaEwlAei/vJ1NH//oc3MNs6Q2Rwt004tlxtjHnROtHviKsf1brjcsTXGVAEeIvWvxb9yueN7m6zgQsfWGONhjNkBnAFWiojLHttMZIVsPrZ5oTCYm7x3Y8XNzDbOkJkc20ntcdIA+ApYnNOhssBVjmtmudyxNcb4AQuBV0Qk9sbVN/mIZcf3Dlld6tiKSIqINCR17vlmxpi6N2ziMsc2E1mz/djmhcIQDVT8y9cVgBP3sI0z3DGHiMReP7UUkR8AT2NMCedFvCuuclwzxdWOrTHGk9RftLNEZNFNNnGZ43unrK52bK8TkUvAGqDTDatc5thed6usOXFs80Jh2AJUN8ZUNcZ4AX2BJTdsswR4Lm0kQgsgRkROOjsomchqjCljjDFpr5uR+t/wvNOTZo6rHNdMcaVjm5ZjMrBHRL64xWYucXwzk9XFjm1JY8x9aa99gMeAvTds5irH9o5Zc+LY5s/Kh92BiCQbY/4PWEHqqJ8pIrLLGDMibX0Q8AOpoxAOAleBF1046zNAgDEmGYgH+kra0ARnM8bMIXVERAljTDTwPqk3x1zquF6Xibwuc2yBh4GBwM6068sA7wCVwOWOb2ayutKxLQtMN8Z4kPpLdJ6IfO+KvxMymTXbj622xFBKKZVBXriUpJRS6i5oYVBKKZWBFgallFIZaGFQSimVgRYGpZRSGWhhUEoplYEWBqVygDFmgjHG1xhzvzFmsjFmQdr7jY0xw63Op9TtaGFQKpsZY4qR2hjzalqn3MHX14nINqCNdemUujMtDEplv4bA7tusTzDGlHZSFqXumhYGpbLApM5c1iHt9SfGmIlAMeDSbT52ESjshHhK3RMtDEplzfvAu8aY/qTOQ/AqqTOYVQEwxhQ3xgQBDxlj/pX2mfLAMQuyKpUpub6JnlI5SUTWpXW2/CfgLyIpxpidQGDa+vPAiOvbp81ZECsi1ywJrFQm6BmDUllgjKlHagfMa2nTWpLW2XKWMcb3Jh8pB/zHiRGVumtaGJS6RyZ1DuBZpM4PHGeM6Xh9nYj8IiJXb/yMiOwXkUNOjKnUXdPCoNQ9SDsbWAS8JiJ7gI+BDywNpVQ20fkYlFJKZaBnDEoppTLQwqCUUioDLQxKKaUy0MKglFIqAy0MSimlMtDCoJRSKgMtDEoppTLQwqCUUioDLQxKKaUy+P8AU91MBNcX2wAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "\n",
    "# 绘制数据点\n",
    "color_seq = ['red' if v==1 else 'blue' for v in y]\n",
    "plt.scatter([i[0] for i in X], [i[1] for i in X], c=color_seq)\n",
    "\n",
    "# 得到x轴的所有点\n",
    "xaxis = np.linspace(0, 3.5)\n",
    "w = clf.coef_[0]\n",
    "\n",
    "# 计算斜率\n",
    "a = -w[0] / w[1]\n",
    "\n",
    "# 得到分离超平面\n",
    "y_sep = a * xaxis - (clf.intercept_[0]) / w[1]\n",
    "\n",
    "# 下边界超平面\n",
    "b = clf.support_vectors_[0]\n",
    "yy_down = a * xaxis + (b[1] - a * b[0])\n",
    "\n",
    "# 上边界超平面\n",
    "b = clf.support_vectors_[-1]\n",
    "yy_up = a * xaxis + (b[1] - a * b[0])\n",
    "\n",
    "# 绘制超平面\n",
    "plt.plot(xaxis, y_sep, 'k-')\n",
    "plt.plot(xaxis, yy_down, 'k--')\n",
    "plt.plot(xaxis, yy_up, 'k--')\n",
    "\n",
    "# 绘制支持向量\n",
    "plt.xlabel('$x^{(1)}$')\n",
    "plt.ylabel('$x^{(2)}$')\n",
    "plt.scatter(clf.support_vectors_[:, 0], clf.support_vectors_[:, 1], \n",
    "            s=150, facecolors='none', edgecolors='k')\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 习题7.3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;线性支持向量机还可以定义为以下形式：\n",
    "$$\n",
    "\\begin{array}{cl} \n",
    "\\displaystyle \\min \\limits_{w,b,\\xi} & \\displaystyle \\frac{1}{2} \\|w\\|^2 + C \\sum_{i=1}^N \\xi_i^2 \\\\\n",
    "\\text{s.t.} & y_i(w \\cdot x_i + b) \\geqslant 1 - \\xi_i, \\quad i=1,2,\\cdots, N \\\\\n",
    "& \\xi_i \\geqslant 0, \\quad i=1,2,\\cdots, N\n",
    "\\end{array}\n",
    "$$\n",
    "试求其对偶形式。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答：**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答思路：**  \n",
    "\n",
    "参考书中第7.2.2节“学习的对偶算法”内容`\n",
    "1. 根据附录C 拉格朗日对偶性，写出拉格朗日函数；\n",
    "2. 对 $L(w,b,\\xi,\\alpha,\\mu)$ 求 $w,b,\\xi$ 的极小；\n",
    "3. 对 $\\displaystyle \\min \\limits_{w,b,\\xi} L(w,b,\\xi,\\alpha,\\mu)$ 求 $\\alpha$ 的极大；\n",
    "4. 整理得到对偶形式。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答步骤：**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第1步：原始问题的拉格朗日函数**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;根据书中附录C拉格朗日对偶性：\n",
    "> 假设$f(x),c_i(x),h_j(x)$是定义在$R^n$上的连续可微函数。考虑约束最优化问题\n",
    "> $$ \\begin{align}\n",
    "\\displaystyle \\min \\limits_{x \\in R^n} \\quad & f(x) \\tag{C.1} \\\\\n",
    "\\text{s.t.} \\quad & c_i(x) \\leqslant 0, \\quad i=1,2,\\cdots, k \\tag{C.2} \\\\\n",
    "\\quad & h_j(x) = 0, \\quad j=1,2,\\cdots, l \\tag{C.3} \n",
    "\\end{align} $$\n",
    "> 称此约束最优化问题为原始最优化问题，或原始问题。\n",
    "> \n",
    "> 引入广义拉格朗日函数\n",
    "> $$ L(x,\\alpha, \\beta) = f(x) + \\sum_{i=1}^k \\alpha_i c_i(x) + \\sum_{j=1}^l \\beta_j h_j(x) \\tag{C.4} $$\n",
    "> 这里，$x=(x^{(1)}, x^{(2)}, \\cdots, x^{(n)})^T \\in R^n$，$\\alpha_i,\\beta_j$是拉格朗日乘子，$\\alpha_i \\geqslant 0$。考虑$x$的函数：\n",
    "> \n",
    "> $$ \\theta_P(x) = \\max \\limits_{\\alpha,\\beta:\\alpha_i \\geqslant 0} L(x, \\alpha, \\beta) \\tag{C.5} $$\n",
    "> 这里，下标$P$表示原始问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;根据书中附录C的原始问题极小化：\n",
    "> 如果考虑极小化问题\n",
    "> $$ \\min \\limits_{x} \\theta_P(x) = \\min \\limits_{x} \\max \\limits_{\\alpha,\\beta:\\alpha_i \\geqslant 0} L(x, \\alpha, \\beta) $$\n",
    "> 它是与原始最优化问题(C.1)~(C.3)等价的，即它们有相同的解。问题 $\\min \\limits_{x} \\max \\limits_{\\alpha,\\beta:\\alpha_i \\geqslant 0} L(x, \\alpha, \\beta)$ 称为广义拉格朗日函数的极小极大问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;根据题意，原始问题为\n",
    "$$\n",
    "\\begin{array}{cl} \n",
    "\\displaystyle \\min \\limits_{w,b,\\xi} & \\displaystyle \\frac{1}{2} \\|w\\|^2 + C \\sum_{i=1}^N \\xi_i^2 \\\\\n",
    "\\text{s.t.} & y_i(w \\cdot x_i + b) \\geqslant 1 - \\xi_i, \\quad i=1,2,\\cdots, N \\\\\n",
    "& \\xi_i \\geqslant 0, \\quad i=1,2,\\cdots, N\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;根据最优化函数的对应关系，可得\n",
    "$$\n",
    "\\left \\{ \\begin{array}{ll}\n",
    "\\displaystyle f(x) = \\frac{1}{2} \\|w\\|^2 + C \\sum_{i=1}^N \\xi_i^2 \\\\\n",
    "c_i^{(1)}(x) = 1 - \\xi_i - y_i(w \\cdot x_i + b), \\quad i = 1,2,\\cdots, N \\\\\n",
    "c_i^{(2)}(x) = - \\xi_i, \\quad i = 1,2,\\cdots, N \n",
    "\\end{array} \\right.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;根据拉格朗日函数的定义，可得原始问题的拉格朗日函数为\n",
    "$$\n",
    "L(w,b,\\xi, \\alpha, \\mu) = \\frac{1}{2} \\|w\\|^2 + C \\sum_{i=1}^N \\xi_i^2 - \\sum_{i=1}^N \\alpha_i(y_i (w \\cdot x_i + b)-1 + \\xi_i) - \\sum_{i=1}^N \\mu_i \\xi_i\n",
    "$$ \n",
    "其中，$\\alpha_i \\geqslant 0, \\mu_i \\geqslant 0$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第2步：对$L(w,b,\\xi,\\alpha,\\mu)$求$w,b,\\xi$的极小**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;根据拉格朗日对偶性，对偶问题是拉格朗日函数的极大极小问题，先对$L(w,b,\\xi,\\alpha,\\mu)$求$w,b,\\xi$的极小，分别对$w,b,\\xi$求偏导，并令导数等于0，由\n",
    "$$\n",
    "\\begin{array}{l}\n",
    "\\displaystyle \\nabla_w L(w,b,\\xi,\\alpha,\\mu)  = w - \\sum_{i=1}^N \\alpha_i y_i x_i = 0 \\\\ \n",
    "\\displaystyle \\nabla_b L(w,b,\\xi,\\alpha,\\mu)  =  -\\sum_{i=1}^N \\alpha_i y_i = 0 \\\\\n",
    "\\displaystyle \\nabla_{\\xi_i} L(w,b,\\xi,\\alpha,\\mu)  = 2C \\xi_i - \\alpha_i - \\mu_i = 0 \n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;可得：\n",
    "$$\n",
    "\\begin{array}{l}\n",
    "\\displaystyle w = \\sum_{i=1}^N \\alpha_i y_i x_i \\\\ \n",
    "\\displaystyle \\sum_{i=1}^N \\alpha_i y_i = 0 \\\\\n",
    "\\displaystyle 2C \\xi_i - \\alpha_i - \\mu_i = 0 \n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;将上式代入到原始问题的拉格朗日函数中，可得\n",
    "$$\n",
    "\\begin{aligned}\n",
    "L(w, b, \\xi, \\alpha, \\mu) \n",
    "&= \\frac{1}{2} \\sum_{i=1}^N \\sum_{j=1}^N \\alpha_i \\alpha_j y_i y_j (x_i \\cdot x_j) +  C \\sum_{i=1}^N \\xi_i^2 - \\sum_{i=1}^N \\alpha_i y_i \\left( \\left( \\sum_{j=1}^N \\alpha_j y_j x_j \\right) \\cdot x_i + b \\right) \\\\\n",
    "& + \\sum_{i=1}^N \\alpha_i - \\sum_{i=1}^N \\alpha_i \\xi_i - \\sum_{i=1}^N \\mu_i \\xi_i \\\\\n",
    "&= -\\frac{1}{2} \\sum_{i=1}^N \\sum_{j=1}^N \\alpha_i \\alpha_j y_i y_j (x_i \\cdot x_j) + \\sum_{i=1}^N \\alpha_i + C \\sum_{i=1}^N \\xi_i^2 - \\sum_{i=1}^N \\alpha_i \\xi_i - \\sum_{i=1}^N \\mu_i \\xi_i \\\\\n",
    "&= -\\frac{1}{2} \\sum_{i=1}^N \\sum_{j=1}^N \\alpha_i \\alpha_j y_i y_j (x_i \\cdot x_j) + \\sum_{i=1}^N \\alpha_i + C \\sum_{i=1}^N \\xi_i^2 - \\sum_{i=1}^N (\\alpha_i + \\mu_i) \\xi_i \\\\\n",
    "&= -\\frac{1}{2} \\sum_{i=1}^N \\sum_{j=1}^N \\alpha_i \\alpha_j y_i y_j (x_i \\cdot x_j) + \\sum_{i=1}^N \\alpha_i + C \\sum_{i=1}^N \\xi_i^2 - \\sum_{i=1}^N \\left( 2C \\xi_i \\right) \\xi_i \\\\\n",
    "&= -\\frac{1}{2} \\sum_{i=1}^N \\sum_{j=1}^N \\alpha_i \\alpha_j y_i y_j (x_i \\cdot x_j) + \\sum_{i=1}^N \\alpha_i + C \\sum_{i=1}^N \\xi_i^2 - 2C \\sum_{i=1}^N \\xi_i^2 \\\\\n",
    "&= -\\frac{1}{2} \\sum_{i=1}^N \\sum_{j=1}^N \\alpha_i \\alpha_j y_i y_j (x_i \\cdot x_j) + \\sum_{i=1}^N \\alpha_i - C \\sum_{i=1}^N \\xi_i^2 \\\\\n",
    "&= -\\frac{1}{2} \\sum_{i=1}^N \\sum_{j=1}^N \\alpha_i \\alpha_j y_i y_j (x_i \\cdot x_j) + \\sum_{i=1}^N \\alpha_i - C \\sum_{i=1}^N \\left(\\frac{1}{4 C^2}(\\alpha_i + \\mu_i)^2 \\right) \\\\\n",
    "&= -\\frac{1}{2} \\sum_{i=1}^N \\sum_{j=1}^N \\alpha_i \\alpha_j y_i y_j (x_i \\cdot x_j) + \\sum_{i=1}^N \\alpha_i - \\frac{1}{4 C}\\sum_{i=1}^N (\\alpha_i + \\mu_i)^2\n",
    "\\end{aligned}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第3步：对$\\displaystyle \\min \\limits_{w,b,\\xi} L(w,b,\\xi,\\alpha,\\mu)$求$\\alpha$的极大**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;根据第2步，对$\\displaystyle \\min \\limits_{w,b,\\xi} L(w,b,\\xi,\\alpha,\\mu)$求$\\alpha$的极大，可得到对偶问题：\n",
    "$$\n",
    "\\begin{array}{cl} \n",
    "\\displaystyle \\max \\limits_{\\alpha} & \\displaystyle -\\frac{1}{2} \\sum_{i=1}^N \\sum_{j=1}^N \\alpha_i \\alpha_j y_i y_j (x_i \\cdot x_j) + \\sum_{i=1}^N \\alpha_i - \\frac{1}{4 C}\\sum_{i=1}^N (\\alpha_i + \\mu_i)^2 \\\\\n",
    "\\text{s.t.} & \\displaystyle \\sum_{i=1}^N \\alpha_i y_i = 0 \\\\\n",
    "& \\displaystyle 2C \\xi_i - \\alpha_i - \\mu_i = 0 \\\\\n",
    "& \\alpha_i \\geqslant 0 ,\\mu_i \\geqslant 0, \\xi_i \\geqslant 0, \\quad i=1,2,\\cdots, N\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第4步：进行公式变换，得到对偶形式**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;再将对目标函数求极大转换为求极小，于是得到原始问题的对偶形式\n",
    "$$\n",
    "\\begin{array}{cl} \n",
    "\\displaystyle \\min \\limits_{\\alpha} & \\displaystyle \\frac{1}{2} \\sum_{i=1}^N \\sum_{j=1}^N \\alpha_i \\alpha_j y_i y_j (x_i \\cdot x_j) - \\sum_{i=1}^N \\alpha_i + \\frac{1}{4 C}\\sum_{i=1}^N (\\alpha_i + \\mu_i)^2 \\\\\n",
    "\\text{s.t.} & \\displaystyle \\sum_{i=1}^N \\alpha_i y_i = 0 \\\\\n",
    "& \\displaystyle 2C \\xi_i - \\alpha_i - \\mu_i = 0 \\\\\n",
    "& \\alpha_i \\geqslant 0 ,\\mu_i \\geqslant 0, \\xi_i \\geqslant 0, \\quad i=1,2,\\cdots, N\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 习题7.4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;证明内积的正整数幂函数：$$K(x,z)=(x \\bullet z)^p$$是正定核函数，这里$p$是正整数，$x,z\\in R^n$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答：**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答思路：**  \n",
    "1. 写出正定核函数的判定依据\n",
    "2. 使用数学归纳法，证明\n",
    "  1. 当$p=1$时，根据定理7.5，证明$K(x, z)=x \\bullet z$是正定核函数\n",
    "  2. 假设当$p=k$且$k>1$时，$K(x, z)=(x \\bullet z)^k$是正定核函数\n",
    "  3. 证明当$p=k+1$时，$K(x, z)=(x \\bullet z)^{k+1}$是正定核函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**解答步骤：**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第1步：列出正定核函数的判定依据**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "根据书中第7章的定理7.5（正定核的充要条件）：\n",
    "\n",
    "> **定理7.5（正定核的充要条件）** 设$K: \\mathcal{X} \\times \\mathcal{X} \\rightarrow R$是对称函数，则$K(x,z)$为正定核函数的充要条件是对任意$x_i \\in \\mathcal{X}, i=1,2,\\cdots, m$，$K(x, z)$对应的Gram矩阵：\n",
    "> $$ K = [K(x_i, x_j)]_{m \\times m} $$\n",
    "> 是半正定矩阵。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**第2步：使用数学归纳法，证明$K(x, z)=(x \\bullet z)^p$是正定核函数**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. 当$p=1$时，$K(x, z)=x \\bullet z$，对任意$c_1,c_2,\\cdots,c_n \\in \\mathbf{R}$，有\n",
    "\n",
    "$$\n",
    "\\begin{aligned} \n",
    "\\sum_{i,j=1}^n c_i c_j K(x_i,x_j) \n",
    "&= \\sum_{i,j=1}^n c_i c_j (x_i \\bullet x_j) \\\\\n",
    "&= \\left(\\sum_{i=1}^m c_i x_i \\right) \\bullet \\left(\\sum_{j=1}^m c_j x_j \\right) \\\\\n",
    "&= \\Bigg\\|\\left( \\sum_{i=1}^m c_i x_i \\right)\\Bigg\\|^2 \\geqslant 0\n",
    "\\end{aligned}\n",
    "$$\n",
    "可得，当$p=1$时，$K(x, z)=x \\bullet z$对应的Gram矩阵是半正定的，根据定理7.5，可知$K(x,z)=x \\bullet z$是正定核函数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. 假设$p=k$且$k$是大于1的正整数时，$K(x, z)=(x \\bullet z)^k$是正定核函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "根据书中第7章的定义7.6的（核函数）：\n",
    "> **定义7.6（核函数）** 设$\\mathcal{X}$是输入空间（欧式空间$R^n$的子集或离散集合），又设$\\mathcal{H}$为特征空间（希尔伯特空间），如果存在一个从$\\mathcal{X}$到$\\mathcal{H}$的映射\n",
    "> $$ \\phi(x):\\mathcal{X} \\rightarrow \\mathcal{H} $$\n",
    "> 使得对所有$x,z \\in \\mathcal{X}$，函数$K(x,z)$满足条件\n",
    "> $$ K(x,z) = \\phi(x) \\bullet \\phi(z) $$\n",
    "> 则称$K(x,z)$为核函数，$\\phi(x)$为映射函数，式中$\\phi(x) \\bullet \\phi(z)$为$\\phi(x)$和$\\phi(z)$的内积。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "故存在一个输入空间为$R^n$，$R^n$到$\\mathcal{H}$的映射\n",
    "$$\n",
    "\\phi(x):R^n \\rightarrow \\mathcal{H}\n",
    "$$\n",
    "使得对所有$x,z \\in R^n$，函数$K(x,z)=(x \\bullet z)^k$满足条件\n",
    "$$\n",
    "K(x,z) = \\phi(x) \\bullet \\phi(z)\n",
    "$$\n",
    "可假设$\\phi(x)=(f_1(x), f_2(x), \\cdots, f_m(x))^T$，其中$x=(x^{(1)}, x^{(2)}, \\cdots, x^{(n)})^T$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. 当$p=k+1$时  \n",
    "$$\n",
    "\\begin{aligned}\n",
    "K(x,z) \n",
    "&= (x \\bullet z)^{k+1} \\\\\n",
    "&= (x \\bullet z)^k (x \\bullet z) \\\\\n",
    "&= (\\phi(x) \\bullet \\phi(z))(x \\bullet z) \\\\\n",
    "&= (f_1(x)f_1(z) + f_2(x)f_2(z) + \\cdots + f_m(x)f_m(z))(x^{(1)}z^{(1)} + x^{(2)}z^{(2)} + \\cdots + x^{(n)}z^{(n)}) \\\\\n",
    "&= f_1(x)f_1(z)(x^{(1)}z^{(1)} + x^{(2)}z^{(2)} + \\cdots + x^{(n)}z^{(n)}) \\\\ \n",
    "& \\quad + f_2(x)f_2(z)(x^{(1)}z^{(1)} + x^{(2)}z^{(2)} + \\cdots + x^{(n)}z^{(n)}) + \\cdots \\\\\n",
    "& \\quad + f_m(x)f_m(z)(x^{(1)}z^{(1)} + x^{(2)}z^{(2)} + \\cdots + x^{(n)}z^{(n)}) \\\\\n",
    "&= (f_1(x)x^{(1)})(f_1(z)z^{(1)}) + (f_1(x)x^{(2)})(f_1(z)z^{(2)}) + \\cdots \\\\ \n",
    "& \\quad + (f_1(x)x^{(n)})(f_1(z)z^{(n)}) \\\\\n",
    "& \\quad + (f_2(x)x^{(1)})(f_2(z)z^{(1)}) + (f_2(x)x^{(2)})(f_2(z)z^{(2)}) + \\cdots \\\\\n",
    "& \\quad + (f_2(x)x^{(n)})(f_2(z)z^{(n)}) + \\cdots \\\\\n",
    "& \\quad + (f_m(x)x^{(1)})(f_m(z)z^{(1)}) + (f_m(x)x^{(2)})(f_m(z)z^{(2)}) + \\cdots \\\\ \n",
    "& \\quad + (f_m(x)x^{(n)})(f_m(z)z^{(n)}) \n",
    "\\end{aligned}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;可得\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\phi'(x) &= (f_1(x)x^{(1)}, f_1(x)x^{(2)}, \\cdots, f_1(x)x^{(n)}, \\\\\n",
    "& \\quad f_2(x)x^{(1)}, f_2(x)x^{(2)}, \\cdots, f_2(x)x^{(n)}, \\\\\n",
    "& \\quad f_m(x)x^{(1)}, \\cdots, f_m(x)x^{(n)})^T\n",
    "\\end{aligned}\n",
    "$$  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;故存在从$R^n$到希尔伯特空间$\\mathcal{H}$的映射$\\phi'(x)$，使得\n",
    "$$\n",
    "K(x,z) = (x \\bullet z)^{k+1} = \\phi'(x) \\bullet \\phi'(z)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;根据《矩阵分析》书中定理7.5.3：\n",
    "\n",
    "> **7.5.3定理** 如果$A,B \\in M_n$是半正定矩阵，则$A \\bullet B$也是半正定矩阵，此外如果$A$和$B$都是正定矩阵，则$A \\bullet B$也是正定矩阵。  \n",
    "> 其中，$A \\bullet B$称为$A$和$B$的Hadamard乘积。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;由根据书中定理7.5，可得$K(x,z)=(x \\bullet z)^{k+1}$是正定核函数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "&emsp;&emsp;根据数学归纳法可得：  \n",
    "&emsp;&emsp;当$p$是正整数，$x,z\\in R^n$时，内积的正整数幂函数：$$K(x,z)=(x \\bullet z)^p$$是正定核函数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 参考文献"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "【1】Roger A.Horn, Charles R.Johnson, 杨奇(译). 矩阵分析[M]. 2005(1):324"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.5"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
